#include<vector>
#include<exception>

template <typename T>
class Tree;

template <typename T>
void swap(Tree<T> & s, Tree<T> & t) {
	std::swap(s . node, t . node);
}

template <typename T>
class Tree {
	T node;
	Tree * left;
	Tree * right;
	Tree * parent;
	
	public:
	
	Tree(T const & t) : node(t), left(0), right(0), parent(0) {}
		
	Tree(Tree const & tree) {
		node = tree . node;
		parent = 0;
		if (tree . left != 0) {
			left = new Tree(* tree . left);
			left -> parent = this;
		}
		else
			left = 0;
		try {
			if (tree . right != 0) {
				right = new Tree(* tree . right);
				right -> parent = this;
			}
		} catch(std::exception & e) {
			delete left;
			throw e;
		}
	}
	
	~Tree() {
		if (left != 0) delete left;
		if (right != 0) delete right;
	}
	
	T & getNode() { return node; }
	T const & getNode() const {return node; }
	Tree * getLeft() {return left; }
	Tree const * getLeft() const {return left; }
	Tree * getRight() {return right; }
	Tree const * getRight() const {return right; }
	Tree * getParent() {return parent; }
	Tree const * getParent() const {return parent; }
	
	void appendLeft(Tree * t) {
		if (left == 0) {
			left = t;
			t -> parent = this;
		}
		else
			throw std::bad_alloc();
	}


	void appendRight(Tree * t) {
		if (right == 0) {
			right = t;
			t -> parent = this;
		}
		else
			throw std::bad_alloc();
	}
	
	void trimLeft() {
		if (left != 0) {
			delete left;
			left = 0;
		}
	}
	
	void trimRight() {
		if (right != 0) {
			delete right;
			right = 0;
		}
	}	
	
	int whichChild() const {
		if (parent == 0)
			return 0;
		else {
			if (parent -> left == this)
				return -1;
			else
				return 1;
		}
	}
	
	friend void swap<>(Tree & s, Tree & t);
	
};

